﻿using System;
using System.Collections.Generic;

namespace Homework21
{
    class Graph
    {
        // 图中的顶点数
        private int vertices;
        // 邻接表，使用字典来存储
        private Dictionary<int, List<Edge>> adjLists;
        // 存储从起点到每个顶点的最短距离
        private int[] distances;

        // 边的结构体，包含目标顶点和权重
        public struct Edge
        {
            public int Destination;
            public int Weight;

            public Edge(int dest, int weight)
            {
                Destination = dest;
                Weight = weight;
            }
        }

        // 构造函数，初始化图的顶点数和邻接表
        public Graph(int vertices)
        {
            this.vertices = vertices;
            adjLists = new Dictionary<int, List<Edge>>();
            distances = new int[vertices];
            for (int i = 0; i < vertices; i++)
            {
                adjLists[i] = new List<Edge>();
            }
        }

        // 添加边的方法，只添加从源点到目标点的边
        public void AddEdge(int source, int destination, int weight)
        {
            adjLists[source].Add(new Edge(destination, weight));
        }

        // Dijkstra算法实现
        public void Dijkstra(int startVertex)
        {
            bool[] visited = new bool[vertices]; // 标记数组，记录顶点是否已确定最短路径
            Array.Fill(distances, int.MaxValue); // 初始化所有顶点的最短距离为无穷大
            distances[startVertex] = 0; // 起点到自身的距离为0

            for (int i = 0; i < vertices; i++) // 对所有顶点进行遍历
            {
                int u = MinDistance(visited); // 选择未访问的顶点中距离最小的顶点
                visited[u] = true; // 标记为已访问

                foreach (var edge in adjLists[u]) // 遍历当前顶点的所有邻接顶点
                {
                    int alt = distances[u] + edge.Weight; // 通过当前顶点到邻接顶点的距离
                    if (alt < distances[edge.Destination]) // 如果这个距离更短，则更新
                    {
                        distances[edge.Destination] = alt; // 更新邻接顶点的最短距离
                    }
                }
            }
        }

        // 选择未访问的顶点中距离最小的顶点
        private int MinDistance(bool[] visited)
        {
            int min = int.MaxValue, minIndex = -1;

            for (int v = 0; v < vertices; v++)
            {
                if (!visited[v] && distances[v] < min)
                {
                    min = distances[v];
                    minIndex = v;
                }
            }

            return minIndex;
        }

        // 打印从起点到所有顶点的最短路径距离
        public void PrintShortestPaths(int startVertex)
        {
            Console.WriteLine("Vertex\t Distance from Source");
            for (int i = 0; i < vertices; i++)
            {
                Console.WriteLine($"{i + 1} \t {distances[i]}");
            }
        }
    }

    class Program
    {
        static void Main()
        {
            Graph graph = new Graph(6); // 创建一个包含6个顶点的图
                                        // 添加边，注意这里是有向图，所以只添加单向边
            graph.AddEdge(0, 1, 250); // v1 到 v2 的边，权重为250
            graph.AddEdge(0, 2, 100); // v1 到 v3 的边，权重为100
            graph.AddEdge(1, 2, 300); // v2 到 v3 的边，权重为300
            graph.AddEdge(1, 3, 275); // v2 到 v4 的边，权重为275
            graph.AddEdge(2, 4, 150); // v3 到 v5 的边，权重为150
            graph.AddEdge(3, 4, 100); // v4 到 v5 的边，权重为100
            graph.AddEdge(3, 5, 200); // v4 到 v6 的边，权重为200
            graph.AddEdge(4, 5, 150); // v5 到 v6 的边，权重为150

            graph.Dijkstra(0); // 从顶点0开始计算最短路径
            graph.PrintShortestPaths(0); // 打印最短路径结果
        }
    }
}

